package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.HashMap;

/**
 * https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 *
 * @author yulongTian
 * @create 2024-05-31 14:10
 */
public class Test33 {
    public static void main(String[] args) {
        LRUCache lRUCache = new Test33().new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        lRUCache.get(1);    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        lRUCache.get(2);    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        lRUCache.get(1);    // 返回 -1 (未找到)
        lRUCache.get(3);    // 返回 3
        lRUCache.get(4);    // 返回 4
        lRUCache.put(4, 5);
        lRUCache.put(3, 8);
        lRUCache.get(3);
        lRUCache.get(4);
    }

    class Node {
        int key;
        int value;
        Node next;
        Node pre;

        Node() {

        }

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    class LRUCache {
        int capacity;
        int size;
        HashMap<Integer, Node> hashMap;
        Node head;
        Node last;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            this.hashMap = new HashMap<>();
        }

        public int get(int key) {
            int res = -1;
            if (hashMap.containsKey(key)) {
                Node node = hashMap.get(key);
                res = node.value;
                // 将key放在头节点
                if (node.pre != null) {
                    // 不是头节点
                    if (node.next == null) {
                        // 是尾节点
                        last = node.pre;
                        last.next = null;
                        //放到头部
                        node.pre = null;
                        node.next = head;
                        head.pre = node;
                        head = node;
                    } else {
                        //不是尾节点
                        Node pre = node.pre;
                        Node next = node.next;
                        pre.next = next;
                        next.pre = pre;
                        //放到头部
                        node.pre = null;
                        node.next = head;
                        head.pre = node;
                        head = node;
                    }
                }
            }
            return res;
        }

        public void put(int key, int value) {
            Node node;
            if (hashMap.containsKey(key)) {
                node = hashMap.get(key);
                node.value = value;
                get(key);
                return;
            } else {
                node = new Node(key, value);
                hashMap.put(key, node);
            }
            if (this.size == 0) {
                head = node;
                last = node;
                this.size++;
                return;
            }
            if (this.size < this.capacity) {
                //放到头部
                node.pre = null;
                node.next = head;
                head.pre = node;
                head = node;
                this.size++;
            } else {
                if (this.capacity == 1) {
                    hashMap.remove(last.key);
                    head = node;
                    last = node;
                    return;
                }
                // 需要换出
                // 去除最后一个
                hashMap.remove(last.key);
                last = last.pre;
                last.next = null;
                // 把新进来的放在头部
                node.next = head;
                head.pre = node;
                head = node;
            }
        }
    }

}
